Former IBM Chief Scientist Ralph Gomory estimated in the mid-1980s that roughly half of all scientific and technical computing cycles ever expended to that time had been used to solve the class of linear optimization problems called Linear Programming problems (LP problems).
This is a staggering statistic given that this area of industry is not a household phrase. However, linear programming applies to many of the important industrial and economic operations that are performed in the world today. From distributing resources throughout the world, to operating power grids, to trading securities, linear programming techniques can be used to find optimum solutions under specified constraints. Thus, linear programming problems are extremely important to the efficient operation of the modern world. Indeed, the first patent ever granted that was associated with software is believed to be Great Britain patent number 1,039,141 titled “A Computer Arranged for the Automatic Solution of Linear Programming Problems” and granted in 1966.
As another example of the importance of linear programming, noted mathematician Martin Grötschel commented in 2006 that: “The development of linear programming is—in my opinion—the most important contribution of the mathematics of the 20th century to the solution of practical problems arising in industry and commerce.”
An example of the use of linear programming can be seen with respect to an industrial plant that has limited resources of equipment, labor, and raw materials. Each of these variables plays a role in how much of each product the plant can produce—(they constrain what is possible). Furthermore, each resource has an associated cost. The profit of such an industrial plant can be modeled through the use of a linear programming problem. And, solving that linear programming problem will amount to optimizing (maximizing) the profit that can be achieved while staying within the constraints of the resources available, and specifying how much of each resource (equipment, labor, and raw materials) should be used to attain the greatest profit for the plant.
As a more detailed example, suppose that in producing two types of containers K and L one uses two machines M1 and M2. To produce a container K, one needs M1 for two minutes and M2 for four minutes. Similarly, production of the L container requires use of M1 for eight minutes and M2 for four minutes. The net profit for L is $45 and the net profit for K is $29. What is the production plan that maximizes the net profit? Linear programming can be utilized to solve this problem by optimizing the amount of profit possible by deciding how many L and how many K containers to build, subject to the constraints of time available on the two machines M1 and M2.
For example, if we produce x1 containers K and x2 containers L per hour, the profit per hour is:f(x1,x2)=29x1+45x2.The constraints are:
2x1+8x2≦60 (resulting from machine M1)
4x1+4x2≦60 (resulting from machine M2)
x1≧0
x2≧0.
Having set up the problem, one can then go on to find the values of x1 and x2 that will produce the greatest profit “f” using linear programming techniques.
Through the years, people have tried to employ computers to solve linear programming problems. This has met with mixed success. For example, in the rather slow world of optimizing a process for an industrial plant, an optimum solution can eventually be obtained heuristically over time, e.g., by trial and error. Depending on the linear objective equation and the linear constraints, the computer optimization process might have to be re-run several times to handle difficulties that might occur initially because of the use of the computer. This will produce results of calculations on the way to a solution that are almost always inexact because of the way computers store numbers. Computers necessarily have to truncate and round numbers off when there are not enough bits available in the representation to give an exact answer. Other difficulties include having the problem cycle, arriving at a clearly incorrect answer, or encountering changing conditions.
These and other difficulties with the use of a computer to do the calculations can lead to arriving at incorrect answers, presenting a proposed solution that is actually infeasible, and incorrectly indicating that there is no feasible solution when there is one that the computer misses because of the accumulated arithmetical errors. Other difficulties may arise from such situations as we will discuss later, including encountering changing conditions (changes, for instance, in prices or constraints) or technical problems in the convergence of the method on a solution that are exacerbated by the arithmetic errors the computer introduces.
Nevertheless, given the relatively slow nature of some industrial plant processes, such a delay did not cause any real practical difficulty since the best solution could be found quickly enough to be economically practical. However, in faster processes that operate in “real time” it becomes much more important to have a reliable method that is not subject to error and that is potentially fast.
Several different methods have been used in the past to approach the solving of linear programs. The more popular of these are known as the Simplex Algorithm, the Revised Simplex Algorithm, the Stored Inverse form of the Revised Simplex Algorithm (SIRSA), and the Implied Inverse form of the Revised Simplex Algorithm (IIRSA).
Algebraic methods for solving linear programs, including all previous versions of methods that are based on the Simplex Algorithm, involve constructing a sequence of equivalent representations of the original problem until a representation is obtained for which the solution is obvious. If the original linear programming problem is of the form Ax=B these methods proceed by attempting to generate a sequence of equivalent systems A1x=b1, A2x=b2, A3x=b3, . . . , Akx=bk until the solution can be read off in an obvious way from the final system. If the calculations that are performed to generate such a sequence of equivalent systems are exact, this technique produces an exactly correct solution.
However, when implemented on digital computers, the calculations are almost never exact in problems that occur in the real world because of errors inherent in the way computers do these calculations. Therefore, while theoretically sound, these traditional algebraic methods fail to produce precisely equivalent representations of the original system Ax=B in actual computer implementations due to the computer error. As a result, all previous versions of simplex-like methods implemented by computer produce results which are (usually) not actually solutions to the original problem. The results they achieve are (usually) fairly close to an exact solution, but they contain errors which are hard to quantify. In certain badly behaved problems that are difficult for computers to handle, called ill-conditioned problems, the answer the computer produces may even be completely unacceptable because these methods may produce, because of the accumulation of computer errors, an answer that presents an optimal solution when there is not one. Or these methods may fail to find an optimal solution when there is one. Moreover, it can be difficult to tell when the answers that these methods produce are defective in one of these ways.
The accumulation of computer errors can be envisioned from the sequence A1x=b1, A2x=b2, A3x=b3, . . . , Akx=bk. This sequence should lead to the optimization of the linear equation system to attain a proposed solution. With the error introduced in each subsequent calculation of Aj due to computer round-off error, one can appreciate that there will be an accumulation of computer error as the processing proceeds to the proposed solution Akx=bk. For example, the computer error in A2 would be propagated to A3 and the computer error in A3 would be propagated to A4. Thus, while an algebraic technique may work exactly when implemented by hand, the introduction of a computer to perform the calculations leads to unavoidable computer errors. The proposed solution to such computer errors in the past has been to use numerical analysis techniques to analyze the solution steps and then try to re-implement the path to the solution that had been arrived at using fewer steps—so as to reduce the accumulated computer error caused by any additional steps. Essentially, this has been a post-hoc attempt to reduce the accumulated error after a proposed solution is achieved—and it requires reattempting a solution. Obviously, such a process of re-attempting a solution introduces a delay in arriving at the solution.
Another type of difficulty is encountered when dealing with linear programming problems whose constraints or other data change during the process of trying to optimize the problem, or after an optimal solution has been obtained. For example, one could envision that during the trading of mortgage backed securities that the price of the security could change quickly, which would affect the optimal solution to the problem. Thus, one would be required to start over from the beginning with the new value for the price. There are many such problems in industry. These problems are known as being “inherently dynamic.”
In addition to the existing simplex-like methods, some alternative methods known as interior point methods have evolved that have gained some attention since the publication of the Simplex Algorithm by George Dantzig in 1947. For example, Leonid G. Khachiyan in 1979 proposed an ellipsoidal method. And, in 1984, Narendra Karmarkar introduced an interior point method for solving linear equations. See, for example, U.S. Pat. No. 4,744,028 issued to AT&T in the name of Narendra Karmarkar.
Other patents related to linear programming include for example, U.S. Pat. No. 5,136,538 to Karmarkar et al. titled “Preconditioned Conjugate Gradient System”; U.S. Pat. No. 6,078,938 to Pan et al. titled “Method and System for Solving Linear Systems”; U.S. Pat. No. 6,694,343 to Forrest et al. titled “Method for Solving a Large Sparse Triangular System of Linear Equations”; U.S. Pat. No. 6,950,844 to Walster et al. titled “Method and Apparatus for Solving Systems of Linear Inequalities”; and U.S. Pat. No. 7,065,545 to Quintero-de-la-Garza titled “Computer Methods of Vector Operation for Reducing Computation Time.”
Nevertheless, difficulties involved with computer implementations of methods for solving linear programming problems remain. For example, as outlined above, the accumulation of computer errors causes a problem. As another example, changing conditions in dynamic problems also cause difficulties.
Thus, there is a need for improvement in the current state of affairs.